/*-------------------------------------------------------------------------
 *
 * spgdoinsert.c
 *	  插入算法的实现
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/spgist/spgdoinsert.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/genam.h"
#include "access/spgist_private.h"
#include "access/spgxlog.h"
#include "access/xloginsert.h"
#include "common/pg_prng.h"
#include "miscadmin.h"
#include "storage/bufmgr.h"
#include "utils/rel.h"


/*
 * SPPageDesc 跟踪我们正在插入的页面的所有信息。在某些情况下，它实际上可以识别一个元组，甚至是一个内嵌元组中的特定节点。但任何字段都可能无效。如果缓存字段有效，则意味着我们在该缓存上保持了锁定和独占锁定。页面指针应在缓存有效时有效。
 */
typedef struct SPPageDesc
{
	BlockNumber blkno;			/* 块号，或 InvalidBlockNumber */
	Buffer		buffer;			/* 页的缓存编号，或 InvalidBuffer */
	Page		page;			/* 指向页面缓存的指针，或 NULL */
	OffsetNumber offnum;		/* 元组的偏移量，或 InvalidOffsetNumber */
	int			node;			/* 内嵌元组中的节点编号，或 -1 */
} SPPageDesc;


/*
 * 在内嵌元组 tup 的第 nodeN 个条目中设置项指针。这用于在移动或拆分操作之后更新父内嵌元组的下链接。
 */
void spgUpdateNodeLink(SpGistInnerTuple fc_tup, int fc_nodeN,
				  BlockNumber fc_blkno, OffsetNumber fc_offset)
{
	int			fc_i;
	SpGistNodeTuple fc_node;

	SGITITERATE(fc_tup, fc_i, fc_node)
	{
		if (fc_i == fc_nodeN)
		{
			ItemPointerSet(&fc_node->t_tid, fc_blkno, fc_offset);
			return;
		}
	}

	elog(ERROR, "failed to find requested node %d in SPGiST inner tuple",
		 fc_nodeN);
}

/*
 * 形成一个新的内嵌元组，包含比给定元组多一个节点，并在节点数组的偏移 "offset" 处插入指定的标签数据。新元组的前缀与旧元组相同。
 *
 * 请注意，新节点最初具有无效的下链接。我们稍后会找到一个页面来指向它。
 */
static SpGistInnerTuple
fc_addNode(SpGistState *fc_state, SpGistInnerTuple fc_tuple, Datum fc_label, int fc_offset)
{
	SpGistNodeTuple fc_node,
			   *fc_nodes;
	int			fc_i;

	/* 如果偏移量为负，则在末尾插入 */
	if (fc_offset < 0)
		fc_offset = fc_tuple->nNodes;
	else if (fc_offset > fc_tuple->nNodes)
		elog(ERROR, "invalid offset for adding node to SPGiST inner tuple");

	fc_nodes = palloc(sizeof(SpGistNodeTuple) * (fc_tuple->nNodes + 1));
	SGITITERATE(fc_tuple, fc_i, fc_node)
	{
		if (fc_i < fc_offset)
			fc_nodes[fc_i] = fc_node;
		else
			fc_nodes[fc_i + 1] = fc_node;
	}

	fc_nodes[fc_offset] = spgFormNodeTuple(fc_state, fc_label, false);

	return spgFormInnerTuple(fc_state,
							 (fc_tuple->prefixSize > 0),
							 SGITDATUM(fc_tuple, fc_state),
							 fc_tuple->nNodes + 1,
							 fc_nodes);
}

/* 用于排序 OffsetNumbers 的 qsort 比较器 */
static int fc_cmpOffsetNumbers(const void *fc_a, const void *fc_b)
{
	if (*(const OffsetNumber *) fc_a == *(const OffsetNumber *) fc_b)
		return 0;
	return (*(const OffsetNumber *) fc_a > *(const OffsetNumber *) fc_b) ? 1 : -1;
}

/*
 * 从索引页面删除多个元组，同时保留元组偏移号码。
 *
 * 给定列表中的第一个元组被类型为 "firststate" (REDIRECT/DEAD/PLACEHOLDER) 的死元组替换；其余元组被类型为 "reststate" 的死元组替换。如果 firststate 或 reststate 为 REDIRECT，则 blkno/offnum 指定链接到的位置。
 *
 * 注意：这在 WAL 回放期间使用，因此请注意不要过于智能化。特别是，它不应该使用 "state"，除非是调用 spgFormDeadTuple()。这也在一个关键段中使用，因此也不能进行 palloc！
 */
void spgPageIndexMultiDelete(SpGistState *fc_state, Page fc_page,
						OffsetNumber *fc_itemnos, int fc_nitems,
						int fc_firststate, int fc_reststate,
						BlockNumber fc_blkno, OffsetNumber fc_offnum)
{
	OffsetNumber fc_firstItem;
	OffsetNumber fc_sortednos[MaxIndexTuplesPerPage];
	SpGistDeadTuple fc_tuple = NULL;
	int			fc_i;

	if (fc_nitems == 0)
		return;					/* 无需操作 */

	/*
	 * 为了提高效率，我们想要使用 PageIndexMultiDelete，这要求目标以排序顺序列出，因此我们必须对 itemnos 数组进行排序。（这也大大简化了重新插入替换元组的数学）。然而，我们不能随意修改调用者的数组，所以我们必须进行复制。
	 */
	memcpy(fc_sortednos, fc_itemnos, sizeof(OffsetNumber) * fc_nitems);
	if (fc_nitems > 1)
		qsort(fc_sortednos, fc_nitems, sizeof(OffsetNumber), fc_cmpOffsetNumbers);

	PageIndexMultiDelete(fc_page, fc_sortednos, fc_nitems);

	fc_firstItem = fc_itemnos[0];

	for (fc_i = 0; fc_i < fc_nitems; fc_i++)
	{
		OffsetNumber fc_itemno = fc_sortednos[fc_i];
		int			fc_tupstate;

		fc_tupstate = (fc_itemno == fc_firstItem) ? fc_firststate : fc_reststate;
		if (fc_tuple == NULL || fc_tuple->tupstate != fc_tupstate)
			fc_tuple = spgFormDeadTuple(fc_state, fc_tupstate, fc_blkno, fc_offnum);

		if (PageAddItem(fc_page, (Item) fc_tuple, fc_tuple->size,
						fc_itemno, false, false) != fc_itemno)
			elog(ERROR, "failed to add item of size %u to SPGiST index page",
				 fc_tuple->size);

		if (fc_tupstate == SPGIST_REDIRECT)
			SpGistPageGetOpaque(fc_page)->nRedirection++;
		else if (fc_tupstate == SPGIST_PLACEHOLDER)
			SpGistPageGetOpaque(fc_page)->nPlaceholder++;
	}
}

/*
 * 更新父内嵌元组的下链接，并标记父缓存为脏（这必须是当前 WAL 操作中对父页面的最后一次更改）。
 */
static void fc_saveNodeLink(Relation fc_index, SPPageDesc *fc_parent,
			 BlockNumber fc_blkno, OffsetNumber fc_offnum)
{
	SpGistInnerTuple fc_innerTuple;

	fc_innerTuple = (SpGistInnerTuple) PageGetItem(fc_parent->page,
												PageGetItemId(fc_parent->page, fc_parent->offnum));

	spgUpdateNodeLink(fc_innerTuple, fc_parent->node, fc_blkno, fc_offnum);

	MarkBufferDirty(fc_parent->buffer);
}

/*
 * 向已知有空间的叶子页面添加一个叶子元组
 */
static void fc_addLeafTuple(Relation fc_index, SpGistState *fc_state, SpGistLeafTuple fc_leafTuple,
			 SPPageDesc *fc_current, SPPageDesc *fc_parent, bool fc_isNulls, bool fc_isNew)
{
	spgxlogAddLeaf fc_xlrec;

	fc_xlrec.newPage = fc_isNew;
	fc_xlrec.storesNulls = fc_isNulls;

	/* 以下内容将在需要时填写 */
	fc_xlrec.offnumLeaf = InvalidOffsetNumber;
	fc_xlrec.offnumHeadLeaf = InvalidOffsetNumber;
	fc_xlrec.offnumParent = InvalidOffsetNumber;
	fc_xlrec.nodeI = 0;

	START_CRIT_SECTION();

	if (fc_current->offnum == InvalidOffsetNumber ||
		SpGistBlockIsRoot(fc_current->blkno))
	{
		/* 元组不是链的一部分 */
		SGLT_SET_NEXTOFFSET(fc_leafTuple, InvalidOffsetNumber);
		fc_current->offnum = SpGistPageAddNewItem(fc_state, fc_current->page,
											   (Item) fc_leafTuple, fc_leafTuple->size,
											   NULL, false);

		fc_xlrec.offnumLeaf = fc_current->offnum;

		/* 如果有的话，必须更新父级的下链接 */
		if (fc_parent->buffer != InvalidBuffer)
		{
			fc_xlrec.offnumParent = fc_parent->offnum;
			fc_xlrec.nodeI = fc_parent->node;

			fc_saveNodeLink(fc_index, fc_parent, fc_current->blkno, fc_current->offnum);
		}
	}
	else
	{
		/*
		 * 元组必须插入到现有链中。我们不能更改链的头地址，但我们不需要追踪整个链以将元组放在末尾；我们可以第二个插入它。
		 *
		 * 此外，"链" 可能仅由一个死元组组成，在这种情况下我们应该就地替换死元组。
		 */
		SpGistLeafTuple fc_head;
		OffsetNumber fc_offnum;

		fc_head = (SpGistLeafTuple) PageGetItem(fc_current->page,
											 PageGetItemId(fc_current->page, fc_current->offnum));
		if (fc_head->tupstate == SPGIST_LIVE)
		{
			SGLT_SET_NEXTOFFSET(fc_leafTuple, SGLT_GET_NEXTOFFSET(fc_head));
			fc_offnum = SpGistPageAddNewItem(fc_state, fc_current->page,
										  (Item) fc_leafTuple, fc_leafTuple->size,
										  NULL, false);

			/*
			 * 重新获取链表的头，因为它可能已经在页面上移动，
			 * 并设置新的第二个元素
			 */
			fc_head = (SpGistLeafTuple) PageGetItem(fc_current->page,
												 PageGetItemId(fc_current->page, fc_current->offnum));
			SGLT_SET_NEXTOFFSET(fc_head, fc_offnum);

			fc_xlrec.offnumLeaf = fc_offnum;
			fc_xlrec.offnumHeadLeaf = fc_current->offnum;
		}
		else if (fc_head->tupstate == SPGIST_DEAD)
		{
			SGLT_SET_NEXTOFFSET(fc_leafTuple, InvalidOffsetNumber);
			PageIndexTupleDelete(fc_current->page, fc_current->offnum);
			if (PageAddItem(fc_current->page,
							(Item) fc_leafTuple, fc_leafTuple->size,
							fc_current->offnum, false, false) != fc_current->offnum)
				elog(ERROR, "failed to add item of size %u to SPGiST index page",
					 fc_leafTuple->size);

			/* WAL重放通过相等的offnums区分这种情况 */
			fc_xlrec.offnumLeaf = fc_current->offnum;
			fc_xlrec.offnumHeadLeaf = fc_current->offnum;
		}
		else
			elog(ERROR, "unexpected SPGiST tuple state: %d", fc_head->tupstate);
	}

	MarkBufferDirty(fc_current->buffer);

	if (RelationNeedsWAL(fc_index) && !fc_state->isBuild)
	{
		XLogRecPtr	fc_recptr;
		int			fc_flags;

		XLogBeginInsert();
		XLogRegisterData((char *) &fc_xlrec, sizeof(fc_xlrec));
		XLogRegisterData((char *) fc_leafTuple, fc_leafTuple->size);

		fc_flags = REGBUF_STANDARD;
		if (fc_xlrec.newPage)
			fc_flags |= REGBUF_WILL_INIT;
		XLogRegisterBuffer(0, fc_current->buffer, fc_flags);
		if (fc_xlrec.offnumParent != InvalidOffsetNumber)
			XLogRegisterBuffer(1, fc_parent->buffer, REGBUF_STANDARD);

		fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_ADD_LEAF);

		PageSetLSN(fc_current->page, fc_recptr);

		/* 仅当我们实际进行了更改时更新父项 */
		if (fc_xlrec.offnumParent != InvalidOffsetNumber)
		{
			PageSetLSN(fc_parent->page, fc_recptr);
		}
	}

	END_CRIT_SECTION();
}

/*
 * 计算从current->offnum开始的链中叶元组的数量和总大小。
 * 将数量返回到*nToSplit，总大小作为函数结果返回。
 *
 * 考虑到根页面时的特殊情况（即，根是一个叶页面，但我们即将第一次进行分割）：
 * 返回假的大值以强制spgdoinsert()采取doPickSplit而不是moveLeafs代码路径。
 * moveLeafs不准备处理根页面。
 */
static int fc_checkSplitConditions(Relation fc_index, SpGistState *fc_state,
					 SPPageDesc *fc_current, int *fc_nToSplit)
{
	int			fc_i,
				fc_n = 0,
				fc_totalSize = 0;

	if (SpGistBlockIsRoot(fc_current->blkno))
	{
		/* 返回不可能的值以强制分割 */
		*fc_nToSplit = BLCKSZ;
		return BLCKSZ;
	}

	fc_i = fc_current->offnum;
	while (fc_i != InvalidOffsetNumber)
	{
		SpGistLeafTuple fc_it;

		Assert(fc_i >= FirstOffsetNumber &&
			   fc_i <= PageGetMaxOffsetNumber(fc_current->page));
		fc_it = (SpGistLeafTuple) PageGetItem(fc_current->page,
										   PageGetItemId(fc_current->page, fc_i));
		if (fc_it->tupstate == SPGIST_LIVE)
		{
			fc_n++;
			fc_totalSize += fc_it->size + sizeof(ItemIdData);
		}
		else if (fc_it->tupstate == SPGIST_DEAD)
		{
			/* 我们可能会看到一个DEAD元组作为第一个/唯一链项 */
			Assert(fc_i == fc_current->offnum);
			Assert(SGLT_GET_NEXTOFFSET(fc_it) == InvalidOffsetNumber);
			/* 不要将其计入结果，因为它不会转移到其他页面 */
		}
		else
			elog(ERROR, "unexpected SPGiST tuple state: %d", fc_it->tupstate);

		fc_i = SGLT_GET_NEXTOFFSET(fc_it);
	}

	*fc_nToSplit = fc_n;

	return fc_totalSize;
}

/*
 * current指向一个我们想要添加newLeafTuple的叶元组链，
 * 但因为没有足够的空间将newLeafTuple添加到其页面，
 * 所以链必须被移动。当链包含非常少的数据时，我们使用这种方法，
 * 因为分割会很低效。我们确信可以将链和newLeafTuple
 * 放在另一个页面上。
 */
static void fc_moveLeafs(Relation fc_index, SpGistState *fc_state,
		  SPPageDesc *fc_current, SPPageDesc *fc_parent,
		  SpGistLeafTuple fc_newLeafTuple, bool fc_isNulls)
{
	int			fc_i,
				fc_nDelete,
				fc_nInsert,
				fc_size;
	Buffer		fc_nbuf;
	Page		fc_npage;
	SpGistLeafTuple fc_it;
	OffsetNumber fc_r = InvalidOffsetNumber,
				fc_startOffset = InvalidOffsetNumber;
	bool		fc_replaceDead = false;
	OffsetNumber *fc_toDelete;
	OffsetNumber *fc_toInsert;
	BlockNumber fc_nblkno;
	spgxlogMoveLeafs fc_xlrec;
	char	   *fc_leafdata,
			   *fc_leafptr;

	/* 这在根页面上不起作用 */
	Assert(fc_parent->buffer != InvalidBuffer);
	Assert(fc_parent->buffer != fc_current->buffer);

	/* 找到要移动的元组，并计算所需的空间 */
	fc_i = PageGetMaxOffsetNumber(fc_current->page);
	fc_toDelete = (OffsetNumber *) palloc(sizeof(OffsetNumber) * fc_i);
	fc_toInsert = (OffsetNumber *) palloc(sizeof(OffsetNumber) * (fc_i + 1));

	fc_size = fc_newLeafTuple->size + sizeof(ItemIdData);

	fc_nDelete = 0;
	fc_i = fc_current->offnum;
	while (fc_i != InvalidOffsetNumber)
	{
		SpGistLeafTuple fc_it;

		Assert(fc_i >= FirstOffsetNumber &&
			   fc_i <= PageGetMaxOffsetNumber(fc_current->page));
		fc_it = (SpGistLeafTuple) PageGetItem(fc_current->page,
										   PageGetItemId(fc_current->page, fc_i));

		if (fc_it->tupstate == SPGIST_LIVE)
		{
			fc_toDelete[fc_nDelete] = fc_i;
			fc_size += fc_it->size + sizeof(ItemIdData);
			fc_nDelete++;
		}
		else if (fc_it->tupstate == SPGIST_DEAD)
		{
			/* 我们可能会看到一个DEAD元组作为第一个/唯一链项 */
			Assert(fc_i == fc_current->offnum);
			Assert(SGLT_GET_NEXTOFFSET(fc_it) == InvalidOffsetNumber);
			/* 我们不想移动它，所以不将其计入大小 */
			fc_toDelete[fc_nDelete] = fc_i;
			fc_nDelete++;
			fc_replaceDead = true;
		}
		else
			elog(ERROR, "unexpected SPGiST tuple state: %d", fc_it->tupstate);

		fc_i = SGLT_GET_NEXTOFFSET(fc_it);
	}

	/* 找到一个可以容纳它们的叶页面 */
	fc_nbuf = SpGistGetBuffer(fc_index, GBUF_LEAF | (fc_isNulls ? GBUF_NULLS : 0),
						   fc_size, &fc_xlrec.newPage);
	fc_npage = BufferGetPage(fc_nbuf);
	fc_nblkno = BufferGetBlockNumber(fc_nbuf);
	Assert(fc_nblkno != fc_current->blkno);

	fc_leafdata = fc_leafptr = palloc(fc_size);

	START_CRIT_SECTION();

	/* 除非它们是死元组，否则将所有旧元组复制到新页面 */
	fc_nInsert = 0;
	if (!fc_replaceDead)
	{
		for (fc_i = 0; fc_i < fc_nDelete; fc_i++)
		{
			fc_it = (SpGistLeafTuple) PageGetItem(fc_current->page,
											   PageGetItemId(fc_current->page, fc_toDelete[fc_i]));
			Assert(fc_it->tupstate == SPGIST_LIVE);

			/*
			 * 更新链链接（注意链的顺序被反转，但我们不关心）。
			 * 我们在这里修改源页面上的元组，但这没关系，因为我们即将删除它。
			 */
			SGLT_SET_NEXTOFFSET(fc_it, fc_r);

			fc_r = SpGistPageAddNewItem(fc_state, fc_npage, (Item) fc_it, fc_it->size,
									 &fc_startOffset, false);

			fc_toInsert[fc_nInsert] = fc_r;
			fc_nInsert++;

			/* 也将修改后的元组保存到leafdata中 */
			memcpy(fc_leafptr, fc_it, fc_it->size);
			fc_leafptr += fc_it->size;
		}
	}

	/* 也添加新元组 */
	SGLT_SET_NEXTOFFSET(fc_newLeafTuple, fc_r);
	fc_r = SpGistPageAddNewItem(fc_state, fc_npage,
							 (Item) fc_newLeafTuple, fc_newLeafTuple->size,
							 &fc_startOffset, false);
	fc_toInsert[fc_nInsert] = fc_r;
	fc_nInsert++;
	memcpy(fc_leafptr, fc_newLeafTuple, fc_newLeafTuple->size);
	fc_leafptr += fc_newLeafTuple->size;

	/*
	 * 现在删除旧元组，为第一个留下重定向指针，除非我们在进行索引构建；
	 * 在这种情况下，不允许有并发扫描，因此我们无需提供重定向。
	 */
	spgPageIndexMultiDelete(fc_state, fc_current->page, fc_toDelete, fc_nDelete,
							fc_state->isBuild ? SPGIST_PLACEHOLDER : SPGIST_REDIRECT,
							SPGIST_PLACEHOLDER,
							fc_nblkno, fc_r);

	/* 更新父项的下链并标记父页面为脏 */
	fc_saveNodeLink(fc_index, fc_parent, fc_nblkno, fc_r);

	/* 也标记叶页面 */
	MarkBufferDirty(fc_current->buffer);
	MarkBufferDirty(fc_nbuf);

	if (RelationNeedsWAL(fc_index) && !fc_state->isBuild)
	{
		XLogRecPtr	fc_recptr;

		/* 准备WAL信息 */
		STORE_STATE(fc_state, fc_xlrec.stateSrc);

		fc_xlrec.nMoves = fc_nDelete;
		fc_xlrec.replaceDead = fc_replaceDead;
		fc_xlrec.storesNulls = fc_isNulls;

		fc_xlrec.offnumParent = fc_parent->offnum;
		fc_xlrec.nodeI = fc_parent->node;

		XLogBeginInsert();
		XLogRegisterData((char *) &fc_xlrec, SizeOfSpgxlogMoveLeafs);
		XLogRegisterData((char *) fc_toDelete,
						 sizeof(OffsetNumber) * fc_nDelete);
		XLogRegisterData((char *) fc_toInsert,
						 sizeof(OffsetNumber) * fc_nInsert);
		XLogRegisterData((char *) fc_leafdata, fc_leafptr - fc_leafdata);

		XLogRegisterBuffer(0, fc_current->buffer, REGBUF_STANDARD);
		XLogRegisterBuffer(1, fc_nbuf, REGBUF_STANDARD | (fc_xlrec.newPage ? REGBUF_WILL_INIT : 0));
		XLogRegisterBuffer(2, fc_parent->buffer, REGBUF_STANDARD);

		fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_MOVE_LEAFS);

		PageSetLSN(fc_current->page, fc_recptr);
		PageSetLSN(fc_npage, fc_recptr);
		PageSetLSN(fc_parent->page, fc_recptr);
	}

	END_CRIT_SECTION();

	/* 更新本地空闲空间缓存并释放新缓冲区 */
	SpGistSetLastUsedPage(fc_index, fc_nbuf);
	UnlockReleaseBuffer(fc_nbuf);
}

/*
 * 用适当的目标更新先前创建的重定向元组
 *
 * 当不方便首先知道目标时，我们使用这个。
 * 元组应该是用“不可行”的元页面目标创建的。
 */
static void fc_setRedirectionTuple(SPPageDesc *fc_current, OffsetNumber fc_position,
					BlockNumber fc_blkno, OffsetNumber fc_offnum)
{
	SpGistDeadTuple fc_dt;

	fc_dt = (SpGistDeadTuple) PageGetItem(fc_current->page,
									   PageGetItemId(fc_current->page, fc_position));
	Assert(fc_dt->tupstate == SPGIST_REDIRECT);
	Assert(ItemPointerGetBlockNumber(&fc_dt->pointer) == SPGIST_METAPAGE_BLKNO);
	ItemPointerSet(&fc_dt->pointer, fc_blkno, fc_offnum);
}

/*
 * 测试用户定义的 picksplit 函数是否未能完成其任务，
 * 即，它将所有叶子元组放入同一个节点。
 * 如果是这样，将元组随机划分为几个节点（都带有相同
 * 标签）并返回 true，以选择此内层元组的 allTheSame 模式。
 *
 * （此代码还用于强制选择 null 的 allTheSame 模式。）
 *
 * 如果我们知道叶子元组无法全部放入一页，则我们
 * 从检查中排除最后一个元组（即迫使分裂的进入新元组）
 * 以查看是否使用了一个以上的节点。这样做的原因是 
 * 如果现有元组仅放入一个链中，即使我们将它们全部移动到空页上，
 * 也仍然没有足够的空间放置新元组，因此我们将陷入
 * picksplit 尝试的无限循环中。
 * 强制 allTheSame 模式可以通过确保旧元组将
 * 被分裂到不同页面中来避免此问题。（读者练习：找出为什么这个
 * 方法即使在只有一个旧元组的情况下也能解决问题。）
 */
static bool fc_checkAllTheSame(spgPickSplitIn *fc_in, spgPickSplitOut *fc_out, bool fc_tooBig,
				bool *fc_includeNew)
{
	int			fc_theNode;
	int			fc_limit;
	int			fc_i;

	/* 暂时假设我们可以包含新的叶子元组 */
	*fc_includeNew = true;

	/* 如果只有新的叶子元组，则不选择 allTheSame 模式 */
	if (fc_in->nTuples <= 1)
		return false;

	/* 如果元组集无法放在一页上，请在测试中忽略新元组 */
	fc_limit = fc_tooBig ? fc_in->nTuples - 1 : fc_in->nTuples;

	/* 检查是否有多个节点被填充 */
	fc_theNode = fc_out->mapTuplesToNodes[0];
	for (fc_i = 1; fc_i < fc_limit; fc_i++)
	{
		if (fc_out->mapTuplesToNodes[fc_i] != fc_theNode)
			return false;
	}

	/* 不，不是，所以覆盖 picksplit 函数的决定 */

	/* 如果新元组在其自己的节点中，则无法包含在分裂中 */
	if (fc_tooBig && fc_out->mapTuplesToNodes[fc_in->nTuples - 1] != fc_theNode)
		*fc_includeNew = false;

	fc_out->nNodes = 8;			/* 子节点的任意数量 */

	/* 随机分配元组到节点（注意我们包含新元组） */
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
		fc_out->mapTuplesToNodes[fc_i] = fc_i % fc_out->nNodes;

	/* opclass 可能不使用节点标签，但如果使用，请重复使用这些标签 */
	if (fc_out->nodeLabels)
	{
		Datum		fc_theLabel = fc_out->nodeLabels[fc_theNode];

		fc_out->nodeLabels = (Datum *) palloc(sizeof(Datum) * fc_out->nNodes);
		for (fc_i = 0; fc_i < fc_out->nNodes; fc_i++)
			fc_out->nodeLabels[fc_i] = fc_theLabel;
	}

	/* 我们不触及前缀或叶子元组数据分配 */

	return true;
}

/*
 * current 指向我们想要添加 newLeafTuple 的叶元组链，但链必须被拆分，因为没有足够的空间将 newLeafTuple 添加到其页面上。
 *
 * 这个函数根据 picksplit 的规则拆分叶元组集，创建一个或多个新的链，这些链分布在当前页面和一个额外的叶页面上（我们假设两个叶页面将是足够的）。创建一个新的内部元组，并且父级下行指针被更新为指向该内部元组，而不是叶链。
 *
 * 在退出时，current 包含新的内部元组的地址。
 *
 * 如果我们在这个函数中成功插入了 newLeafTuple，则返回 true；如果调用者仍然需要执行此操作（意味着可能需要另一个 picksplit 操作），则返回 false。如果 picksplit 结果非常不平衡，或者如果 newLeafTuple 就是太大而无法适应页面，可能会发生失败。因为我们强制 picksplit 结果至少为两个链，每个循环将至少从链中去掉一个叶元组，因此如果缺乏平衡是问题的话，循环最终将会终止。如果元组太大，我们假设重复的 picksplit 操作最终将通过重复前缀剥离使其变得足够小。然而，损坏的操作类别可能会使这个变成无限循环，因此 spgdoinsert() 检查每次叶数据是否变得更小。
 */
static bool fc_doPickSplit(Relation fc_index, SpGistState *fc_state,
			SPPageDesc *fc_current, SPPageDesc *fc_parent,
			SpGistLeafTuple fc_newLeafTuple,
			int fc_level, bool fc_isNulls, bool fc_isNew)
{
	bool		fc_insertedNew = false;
	spgPickSplitIn fc_in;
	spgPickSplitOut fc_out;
	FmgrInfo   *fc_procinfo;
	bool		fc_includeNew;
	int			fc_i,
				fc_max,
				fc_n;
	SpGistInnerTuple fc_innerTuple;
	SpGistNodeTuple fc_node,
			   *fc_nodes;
	Buffer		fc_newInnerBuffer,
				fc_newLeafBuffer;
	uint8	   *fc_leafPageSelect;
	int		   *fc_leafSizes;
	OffsetNumber *fc_toDelete;
	OffsetNumber *fc_toInsert;
	OffsetNumber fc_redirectTuplePos = InvalidOffsetNumber;
	OffsetNumber fc_startOffsets[2];
	SpGistLeafTuple *fc_oldLeafs;
	SpGistLeafTuple *fc_newLeafs;
	Datum		fc_leafDatums[INDEX_MAX_KEYS];
	bool		fc_leafIsnulls[INDEX_MAX_KEYS];
	int			fc_spaceToDelete;
	int			fc_currentFreeSpace;
	int			fc_totalLeafSizes;
	bool		fc_allTheSame;
	spgxlogPickSplit fc_xlrec;
	char	   *fc_leafdata,
			   *fc_leafptr;
	SPPageDesc	fc_saveCurrent;
	int			fc_nToDelete,
				fc_nToInsert,
				fc_maxToInclude;

	fc_in.level = fc_level;

	/*
	 * 分配每个叶元组的工作数组，大小为可能的最大值
	 */
	fc_max = PageGetMaxOffsetNumber(fc_current->page);
	fc_n = fc_max + 1;
	fc_in.datums = (Datum *) palloc(sizeof(Datum) * fc_n);
	fc_toDelete = (OffsetNumber *) palloc(sizeof(OffsetNumber) * fc_n);
	fc_toInsert = (OffsetNumber *) palloc(sizeof(OffsetNumber) * fc_n);
	fc_oldLeafs = (SpGistLeafTuple *) palloc(sizeof(SpGistLeafTuple) * fc_n);
	fc_newLeafs = (SpGistLeafTuple *) palloc(sizeof(SpGistLeafTuple) * fc_n);
	fc_leafPageSelect = (uint8 *) palloc(sizeof(uint8) * fc_n);

	STORE_STATE(fc_state, fc_xlrec.stateSrc);

	/*
	 * 形成将作为拆分结果分配的叶元组列表；还要计算将从当前释放的空间量。
	 * （请注意，在非根情况下，我们不会实际删除旧元组，而只是用重定向或占位符替换它们。）
	 */
	fc_nToInsert = 0;
	fc_nToDelete = 0;
	fc_spaceToDelete = 0;
	if (SpGistBlockIsRoot(fc_current->blkno))
	{
		/*
		 * 我们正在拆分根（到目前为止，它也是一个叶页面）。
		 * 它的元组是没有链接的，因此顺序扫描以获取它们全部。我们忽略 current->offnum 的原始值。
		 */
		for (fc_i = FirstOffsetNumber; fc_i <= fc_max; fc_i++)
		{
			SpGistLeafTuple fc_it;

			fc_it = (SpGistLeafTuple) PageGetItem(fc_current->page,
											   PageGetItemId(fc_current->page, fc_i));
			if (fc_it->tupstate == SPGIST_LIVE)
			{
				fc_in.datums[fc_nToInsert] =
					fc_isNulls ? (Datum) 0 : SGLTDATUM(fc_it, fc_state);
				fc_oldLeafs[fc_nToInsert] = fc_it;
				fc_nToInsert++;
				fc_toDelete[fc_nToDelete] = fc_i;
				fc_nToDelete++;
				/* 我们将完全删除该元组，因此计算完整空间 */
				fc_spaceToDelete += fc_it->size + sizeof(ItemIdData);
			}
			else				/* 根上的元组应该是活动的 */
				elog(ERROR, "unexpected SPGiST tuple state: %d", fc_it->tupstate);
		}
	}
	else
	{
		/* 正常情况，只需收集链中的叶元组 */
		fc_i = fc_current->offnum;
		while (fc_i != InvalidOffsetNumber)
		{
			SpGistLeafTuple fc_it;

			Assert(fc_i >= FirstOffsetNumber && fc_i <= fc_max);
			fc_it = (SpGistLeafTuple) PageGetItem(fc_current->page,
											   PageGetItemId(fc_current->page, fc_i));
			if (fc_it->tupstate == SPGIST_LIVE)
			{
				fc_in.datums[fc_nToInsert] =
					fc_isNulls ? (Datum) 0 : SGLTDATUM(fc_it, fc_state);
				fc_oldLeafs[fc_nToInsert] = fc_it;
				fc_nToInsert++;
				fc_toDelete[fc_nToDelete] = fc_i;
				fc_nToDelete++;
				/* 我们不会删除该元组，只是用死元组替换 */
				Assert(fc_it->size >= SGDTSIZE);
				fc_spaceToDelete += fc_it->size - SGDTSIZE;
			}
			else if (fc_it->tupstate == SPGIST_DEAD)
			{
				/* 我们可能会看到一个DEAD元组作为第一个/唯一链项 */
				Assert(fc_i == fc_current->offnum);
				Assert(SGLT_GET_NEXTOFFSET(fc_it) == InvalidOffsetNumber);
				fc_toDelete[fc_nToDelete] = fc_i;
				fc_nToDelete++;
				/* 用重定向替换将不会节省空间 */
			}
			else
				elog(ERROR, "unexpected SPGiST tuple state: %d", fc_it->tupstate);

			fc_i = SGLT_GET_NEXTOFFSET(fc_it);
		}
	}
	fc_in.nTuples = fc_nToInsert;

	/*
	 * 我们可能实际上不会插入新元组，因为由于值太大可能需要另一个 picksplit，
	 * 但我们将尝试分配足够的空间来包含它；并且无论如何，它必须包含在 picksplit 函数的输入中。因此，暂时不要增加 nToInsert。
	 */
	fc_in.datums[fc_in.nTuples] =
		fc_isNulls ? (Datum) 0 : SGLTDATUM(fc_newLeafTuple, fc_state);
	fc_oldLeafs[fc_in.nTuples] = fc_newLeafTuple;
	fc_in.nTuples++;

	memset(&fc_out, 0, sizeof(fc_out));

	if (!fc_isNulls)
	{
		/*
		 * 使用用户定义的方法执行拆分。
		 */
		fc_procinfo = index_getprocinfo(fc_index, 1, SPGIST_PICKSPLIT_PROC);
		FunctionCall2Coll(fc_procinfo,
						  fc_index->rd_indcollation[0],
						  PointerGetDatum(&fc_in),
						  PointerGetDatum(&fc_out));

		/*
		 * 形成新的叶元组并计算所需的总空间。
		 */
		fc_totalLeafSizes = 0;
		for (fc_i = 0; fc_i < fc_in.nTuples; fc_i++)
		{
			if (fc_state->leafTupDesc->natts > 1)
				spgDeformLeafTuple(fc_oldLeafs[fc_i],
								   fc_state->leafTupDesc,
								   fc_leafDatums,
								   fc_leafIsnulls,
								   fc_isNulls);

			fc_leafDatums[spgKeyColumn] = fc_out.leafTupleDatums[fc_i];
			fc_leafIsnulls[spgKeyColumn] = false;

			fc_newLeafs[fc_i] = spgFormLeafTuple(fc_state, &fc_oldLeafs[fc_i]->heapPtr,
										   fc_leafDatums,
										   fc_leafIsnulls);
			fc_totalLeafSizes += fc_newLeafs[fc_i]->size + sizeof(ItemIdData);
		}
	}
	else
	{
		/*
		 * 执行虚拟拆分，将所有元组放入一个节点。
		 * checkAllTheSame 将覆盖此操作并强制 allTheSame 模式。
		 */
		fc_out.hasPrefix = false;
		fc_out.nNodes = 1;
		fc_out.nodeLabels = NULL;
		fc_out.mapTuplesToNodes = palloc0(sizeof(int) * fc_in.nTuples);

		/*
		 * 形成新的叶元组并计算所需的总空间。
		 */
		fc_totalLeafSizes = 0;
		for (fc_i = 0; fc_i < fc_in.nTuples; fc_i++)
		{
			if (fc_state->leafTupDesc->natts > 1)
				spgDeformLeafTuple(fc_oldLeafs[fc_i],
								   fc_state->leafTupDesc,
								   fc_leafDatums,
								   fc_leafIsnulls,
								   fc_isNulls);

			/*
			 * Nulls树只能包含null键值。
			 */
			fc_leafDatums[spgKeyColumn] = (Datum) 0;
			fc_leafIsnulls[spgKeyColumn] = true;

			fc_newLeafs[fc_i] = spgFormLeafTuple(fc_state, &fc_oldLeafs[fc_i]->heapPtr,
										   fc_leafDatums,
										   fc_leafIsnulls);
			fc_totalLeafSizes += fc_newLeafs[fc_i]->size + sizeof(ItemIdData);
		}
	}

	/*
	 * 检查picksplit函数是否未能分离值，
	 * 即将它们全部放入同一个子节点。如果是这样，选择allTheSame
	 * 模式，并创建一个随机分裂。有关
	 * checkAllTheSame的注释说明了为什我们需要知道新的叶子元组是否可以
	 * 放在一页上。
	 */
	fc_allTheSame = fc_checkAllTheSame(&fc_in, &fc_out,
								 fc_totalLeafSizes > SPGIST_PAGE_CAPACITY,
								 &fc_includeNew);

	/*
	 * 如果checkAllTheSame决定我们必须排除新的元组，不要
	 * 进一步考虑它。
	 */
	if (fc_includeNew)
		fc_maxToInclude = fc_in.nTuples;
	else
	{
		fc_maxToInclude = fc_in.nTuples - 1;
		fc_totalLeafSizes -= fc_newLeafs[fc_in.nTuples - 1]->size + sizeof(ItemIdData);
	}

	/*
	 * 为每个节点分配工作数组。由于checkAllTheSame可能会将
	 * out.nNodes替换为大于输入页面上元组数量的值，
	 * 我们不能在这里之前分配这些数组。
	 */
	fc_nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * fc_out.nNodes);
	fc_leafSizes = (int *) palloc0(sizeof(int) * fc_out.nNodes);

	/*
	 * 形成内部元组及其自身的节点
	 */
	for (fc_i = 0; fc_i < fc_out.nNodes; fc_i++)
	{
		Datum		fc_label = (Datum) 0;
		bool		fc_labelisnull = (fc_out.nodeLabels == NULL);

		if (!fc_labelisnull)
			fc_label = fc_out.nodeLabels[fc_i];
		fc_nodes[fc_i] = spgFormNodeTuple(fc_state, fc_label, fc_labelisnull);
	}
	fc_innerTuple = spgFormInnerTuple(fc_state,
								   fc_out.hasPrefix, fc_out.prefixDatum,
								   fc_out.nNodes, fc_nodes);
	fc_innerTuple->allTheSame = fc_allTheSame;

	/*
	 * 更新nodes[]数组以指向新形成的innerTuple，以便
	 * 我们可以在下面调整它们的下行链接。
	 */
	SGITITERATE(fc_innerTuple, fc_i, fc_node)
	{
		fc_nodes[fc_i] = fc_node;
	}

	/*
	 * 重新扫描新的叶子元组，并统计每个节点下所需的空间。
	 */
	for (fc_i = 0; fc_i < fc_maxToInclude; fc_i++)
	{
		fc_n = fc_out.mapTuplesToNodes[fc_i];
		if (fc_n < 0 || fc_n >= fc_out.nNodes)
			elog(ERROR, "inconsistent result of SPGiST picksplit function");
		fc_leafSizes[fc_n] += fc_newLeafs[fc_i]->size + sizeof(ItemIdData);
	}

	/*
	 * 为了进行分裂，我们必须插入一个新的内部元组，不能放在
	 * 叶子页上；而且除非我们正在分裂根页，否则我们必须更新
	 * 父元组的下行链接以指向内部元组。如果有空间，我们将把
	 * 新的内部元组放在与父元组相同的页面上，否则我们需要
	 * 另一个非叶子缓冲区。但如果父页面是根页面，我们不能在
	 * 那里添加新的内部元组，因为根页面只能有一个内部元组。
	 */
	fc_xlrec.initInner = false;
	if (fc_parent->buffer != InvalidBuffer &&
		!SpGistBlockIsRoot(fc_parent->blkno) &&
		(SpGistPageGetFreeSpace(fc_parent->page, 1) >=
		 fc_innerTuple->size + sizeof(ItemIdData)))
	{
		/* 新的内部元组将适合父页面 */
		fc_newInnerBuffer = fc_parent->buffer;
	}
	else if (fc_parent->buffer != InvalidBuffer)
	{
		/* 将元组发送到具有下一个三重奇偶性（见README）的页面 */
		fc_newInnerBuffer = SpGistGetBuffer(fc_index,
										 GBUF_INNER_PARITY(fc_parent->blkno + 1) |
										 (fc_isNulls ? GBUF_NULLS : 0),
										 fc_innerTuple->size + sizeof(ItemIdData),
										 &fc_xlrec.initInner);
	}
	else
	{
		/* 根页面分裂...内部元组将进入根页面 */
		fc_newInnerBuffer = InvalidBuffer;
	}

	/*
	 * 从现有元组转换的新叶子元组应该需要相同或更少的空间，
	 * 因此应该全部适合一页
	 * （虽然这不一定是当前页面，因为我们不能
	 * 删除旧的元组，而只能用占位符替换它们）。
	 * 然而，传入的新元组也可能不适合，在这种情况下，我们
	 * 可能需要另一个picksplit周期来进一步缩减它。
	 *
	 * 如果没有足够的空间将所有内容放回当前页面，
	 * 那么我们将根据每个节点的情况决定哪些元组去新页面。
	 * （我们这样做是因为叶子元组链不能跨页面，因此我们必须
	 * 将属于同一父节点的所有叶子元组放在同一
	 * 页面上。）
	 *
	 * 如果我们正在分裂根页面（将其从叶子页面变为内部页面），
	 * 则没有叶子元组可以返回到当前页面；它们必须都去别的地方。
	 */
	if (!SpGistBlockIsRoot(fc_current->blkno))
		fc_currentFreeSpace = PageGetExactFreeSpace(fc_current->page) + fc_spaceToDelete;
	else
		fc_currentFreeSpace = 0;	/* 防止将任何元组分配到当前页面 */

	fc_xlrec.initDest = false;

	if (fc_totalLeafSizes <= fc_currentFreeSpace)
	{
		/* 所有叶子元组将适合当前页面 */
		fc_newLeafBuffer = InvalidBuffer;
		/* 如果允许，则将新叶子元组标记为已包含在插入中 */
		if (fc_includeNew)
		{
			fc_nToInsert++;
			fc_insertedNew = true;
		}
		for (fc_i = 0; fc_i < fc_nToInsert; fc_i++)
			fc_leafPageSelect[fc_i] = 0;	/* 表示当前页面 */
	}
	else if (fc_in.nTuples == 1 && fc_totalLeafSizes > SPGIST_PAGE_CAPACITY)
	{
		/*
		 * 我们尝试通过重复后缀分割一个长值，但
		 * 现在还无法适应。不要费心分配一个我们无法使用的
		 * 第二个叶子缓冲区。
		 */
		fc_newLeafBuffer = InvalidBuffer;
		Assert(fc_includeNew);
		Assert(fc_nToInsert == 0);
	}
	else
	{
		/* 我们需要另一个叶子页面 */
		uint8	   *fc_nodePageSelect;
		int			fc_curspace;
		int			fc_newspace;

		fc_newLeafBuffer = SpGistGetBuffer(fc_index,
										GBUF_LEAF | (fc_isNulls ? GBUF_NULLS : 0),
										Min(fc_totalLeafSizes,
											SPGIST_PAGE_CAPACITY),
										&fc_xlrec.initDest);

		/*
		 * 尝试将节点组分配到两个页面。即使 totalLeafSizes 小于可用空间，
		 * 我们可能仍然会失败，因为我们不能跨页面拆分一个组。
		 */
		fc_nodePageSelect = (uint8 *) palloc(sizeof(uint8) * fc_out.nNodes);

		fc_curspace = fc_currentFreeSpace;
		fc_newspace = PageGetExactFreeSpace(BufferGetPage(fc_newLeafBuffer));
		for (fc_i = 0; fc_i < fc_out.nNodes; fc_i++)
		{
			if (fc_leafSizes[fc_i] <= fc_curspace)
			{
				fc_nodePageSelect[fc_i] = 0;	/* 表示当前页面 */
				fc_curspace -= fc_leafSizes[fc_i];
			}
			else
			{
				fc_nodePageSelect[fc_i] = 1;	/* 表示新的叶子页面 */
				fc_newspace -= fc_leafSizes[fc_i];
			}
		}
		if (fc_curspace >= 0 && fc_newspace >= 0)
		{
			/* 成功分配，因此我们可以包含新的叶子元组 */
			if (fc_includeNew)
			{
				fc_nToInsert++;
				fc_insertedNew = true;
			}
		}
		else if (fc_includeNew)
		{
			/* 我们必须将新的叶子元组从分割中排除 */
			int			fc_nodeOfNewTuple = fc_out.mapTuplesToNodes[fc_in.nTuples - 1];

			fc_leafSizes[fc_nodeOfNewTuple] -=
				fc_newLeafs[fc_in.nTuples - 1]->size + sizeof(ItemIdData);

			/* 重复节点分配过程 --- 现在应该成功 */
			fc_curspace = fc_currentFreeSpace;
			fc_newspace = PageGetExactFreeSpace(BufferGetPage(fc_newLeafBuffer));
			for (fc_i = 0; fc_i < fc_out.nNodes; fc_i++)
			{
				if (fc_leafSizes[fc_i] <= fc_curspace)
				{
					fc_nodePageSelect[fc_i] = 0;	/* 表示当前页面 */
					fc_curspace -= fc_leafSizes[fc_i];
				}
				else
				{
					fc_nodePageSelect[fc_i] = 1;	/* 表示新的叶子页面 */
					fc_newspace -= fc_leafSizes[fc_i];
				}
			}
			if (fc_curspace < 0 || fc_newspace < 0)
				elog(ERROR, "failed to divide leaf tuple groups across pages");
		}
		else
		{
			/* 哦，我们已经排除了新的元组 ... 不应该到这里来 */
			elog(ERROR, "failed to divide leaf tuple groups across pages");
		}
		/* 扩展每个节点的分配以显示每个叶子元组 */
		for (fc_i = 0; fc_i < fc_nToInsert; fc_i++)
		{
			fc_n = fc_out.mapTuplesToNodes[fc_i];
			fc_leafPageSelect[fc_i] = fc_nodePageSelect[fc_n];
		}
	}

	/* 开始准备 WAL 记录 */
	fc_xlrec.nDelete = 0;
	fc_xlrec.initSrc = fc_isNew;
	fc_xlrec.storesNulls = fc_isNulls;
	fc_xlrec.isRootSplit = SpGistBlockIsRoot(fc_current->blkno);

	fc_leafdata = fc_leafptr = (char *) palloc(fc_totalLeafSizes);

	/* 在这里我们开始对目标页面进行更改 */
	START_CRIT_SECTION();

	/*
	 * 从当前缓冲区删除旧的叶子元组，除非我们正在分割
	 * 根；在那种情况下没有必要，因为我们下面会重新初始化页面。
	 * 我们首先这样做是为了腾出空间重新插入新的叶子元组。
	 */
	if (!SpGistBlockIsRoot(fc_current->blkno))
	{
		/*
		 * 初始化缓冲区而不是删除单个元组，但只有在
		 * 没有其他活动元组并且仅在构建期间；否则
		 * 我们需要为并发扫描设置重定向元组。
		 */
		if (fc_state->isBuild &&
			fc_nToDelete + SpGistPageGetOpaque(fc_current->page)->nPlaceholder ==
			PageGetMaxOffsetNumber(fc_current->page))
		{
			SpGistInitBuffer(fc_current->buffer,
							 SPGIST_LEAF | (fc_isNulls ? SPGIST_NULLS : 0));
			fc_xlrec.initSrc = true;
		}
		else if (fc_isNew)
		{
			/* 不要将新初始化的缓冲区暴露为备份块 */
			Assert(fc_nToDelete == 0);
		}
		else
		{
			fc_xlrec.nDelete = fc_nToDelete;

			if (!fc_state->isBuild)
			{
				/*
				 * 需要创建重定向元组（它将指向新的内部
				 * 元组），但现在新的元组位置尚未确定。
				 * 所以，将重定向指针设置为“不可行”值 
				 * 并记住其位置，以便稍后更新元组。
				 */
				if (fc_nToDelete > 0)
					fc_redirectTuplePos = fc_toDelete[0];
				spgPageIndexMultiDelete(fc_state, fc_current->page,
										fc_toDelete, fc_nToDelete,
										SPGIST_REDIRECT,
										SPGIST_PLACEHOLDER,
										SPGIST_METAPAGE_BLKNO,
										FirstOffsetNumber);
			}
			else
			{
				/*
				 * 在索引构建期间没有并发搜索，因此我们
				 * 不需要创建重定向元组。
				 */
				spgPageIndexMultiDelete(fc_state, fc_current->page,
										fc_toDelete, fc_nToDelete,
										SPGIST_PLACEHOLDER,
										SPGIST_PLACEHOLDER,
										InvalidBlockNumber,
										InvalidOffsetNumber);
			}
		}
	}

	/*
	 * 将叶子元组放置在正确的页面上，并更新 innerTuple 的
	 * 节点中的下行链接。
	 */
	fc_startOffsets[0] = fc_startOffsets[1] = InvalidOffsetNumber;
	for (fc_i = 0; fc_i < fc_nToInsert; fc_i++)
	{
		SpGistLeafTuple fc_it = fc_newLeafs[fc_i];
		Buffer		fc_leafBuffer;
		BlockNumber fc_leafBlock;
		OffsetNumber fc_newoffset;

		/* 它将去哪个页面？ */
		fc_leafBuffer = fc_leafPageSelect[fc_i] ? fc_newLeafBuffer : fc_current->buffer;
		fc_leafBlock = BufferGetBlockNumber(fc_leafBuffer);

		/* 将元组链接到其节点的正确链中 */
		fc_n = fc_out.mapTuplesToNodes[fc_i];

		if (ItemPointerIsValid(&fc_nodes[fc_n]->t_tid))
		{
			Assert(ItemPointerGetBlockNumber(&fc_nodes[fc_n]->t_tid) == fc_leafBlock);
			SGLT_SET_NEXTOFFSET(fc_it, ItemPointerGetOffsetNumber(&fc_nodes[fc_n]->t_tid));
		}
		else
			SGLT_SET_NEXTOFFSET(fc_it, InvalidOffsetNumber);

		/* 将其插入页面 */
		fc_newoffset = SpGistPageAddNewItem(fc_state, BufferGetPage(fc_leafBuffer),
										 (Item) fc_it, fc_it->size,
										 &fc_startOffsets[fc_leafPageSelect[fc_i]],
										 false);
		fc_toInsert[fc_i] = fc_newoffset;

		/* ... 并完成链链接 */
		ItemPointerSet(&fc_nodes[fc_n]->t_tid, fc_leafBlock, fc_newoffset);

		/* 还将叶子元组复制到 WAL 数据中 */
		memcpy(fc_leafptr, fc_newLeafs[fc_i], fc_newLeafs[fc_i]->size);
		fc_leafptr += fc_newLeafs[fc_i]->size;
	}

	/*
	 * 我们已经完成了对其他叶子缓冲区（如果有的话）的修改，
	 * 所以将其标记为脏。当前的缓冲区将在下面标记，
	 * 在我们完全完成修改之后。
	 */
	if (fc_newLeafBuffer != InvalidBuffer)
	{
		MarkBufferDirty(fc_newLeafBuffer);
	}

	/* 记住当前缓冲区，因为我们即将改变“当前” */
	fc_saveCurrent = *fc_current;

	/*
	 * 存储新的 innerTuple
	 */
	if (fc_newInnerBuffer == fc_parent->buffer && fc_newInnerBuffer != InvalidBuffer)
	{
		/*
		 * 新的内元组将进入父页面
		 */
		Assert(fc_current->buffer != fc_parent->buffer);

		/* 将“当前”指向新的内元组 */
		fc_current->blkno = fc_parent->blkno;
		fc_current->buffer = fc_parent->buffer;
		fc_current->page = fc_parent->page;
		fc_xlrec.offnumInner = fc_current->offnum =
			SpGistPageAddNewItem(fc_state, fc_current->page,
								 (Item) fc_innerTuple, fc_innerTuple->size,
								 NULL, false);

		/*
		 * 更新父节点链接并标记父页面为脏
		 */
		fc_xlrec.innerIsParent = true;
		fc_xlrec.offnumParent = fc_parent->offnum;
		fc_xlrec.nodeI = fc_parent->node;
		fc_saveNodeLink(fc_index, fc_parent, fc_current->blkno, fc_current->offnum);

		/*
		 * 更新重定向链接（在旧的当前缓冲区中）
		 */
		if (fc_redirectTuplePos != InvalidOffsetNumber)
			fc_setRedirectionTuple(&fc_saveCurrent, fc_redirectTuplePos,
								fc_current->blkno, fc_current->offnum);

		/* 完成修改旧的当前缓冲区，标记为脏 */
		MarkBufferDirty(fc_saveCurrent.buffer);
	}
	else if (fc_parent->buffer != InvalidBuffer)
	{
		/*
		 * 新的内元组将在新的页面上存储
		 */
		Assert(fc_newInnerBuffer != InvalidBuffer);

		/* 将“当前”指向新的内元组 */
		fc_current->buffer = fc_newInnerBuffer;
		fc_current->blkno = BufferGetBlockNumber(fc_current->buffer);
		fc_current->page = BufferGetPage(fc_current->buffer);
		fc_xlrec.offnumInner = fc_current->offnum =
			SpGistPageAddNewItem(fc_state, fc_current->page,
								 (Item) fc_innerTuple, fc_innerTuple->size,
								 NULL, false);

		/* 完成修改新当前缓冲区，标记为脏 */
		MarkBufferDirty(fc_current->buffer);

		/*
		 * 更新父节点链接并标记父页面为脏
		 */
		fc_xlrec.innerIsParent = (fc_parent->buffer == fc_current->buffer);
		fc_xlrec.offnumParent = fc_parent->offnum;
		fc_xlrec.nodeI = fc_parent->node;
		fc_saveNodeLink(fc_index, fc_parent, fc_current->blkno, fc_current->offnum);

		/*
		 * 更新重定向链接（在旧的当前缓冲区中）
		 */
		if (fc_redirectTuplePos != InvalidOffsetNumber)
			fc_setRedirectionTuple(&fc_saveCurrent, fc_redirectTuplePos,
								fc_current->blkno, fc_current->offnum);

		/* 完成修改旧的当前缓冲区，标记为脏 */
		MarkBufferDirty(fc_saveCurrent.buffer);
	}
	else
	{
		/*
		 * 拆分根页面，原本是叶子但现在变为内部页面
		 * （因此“当前”继续指向它）
		 */
		Assert(SpGistBlockIsRoot(fc_current->blkno));
		Assert(fc_redirectTuplePos == InvalidOffsetNumber);

		SpGistInitBuffer(fc_current->buffer, (fc_isNulls ? SPGIST_NULLS : 0));
		fc_xlrec.initInner = true;
		fc_xlrec.innerIsParent = false;

		fc_xlrec.offnumInner = fc_current->offnum =
			PageAddItem(fc_current->page, (Item) fc_innerTuple, fc_innerTuple->size,
						InvalidOffsetNumber, false, false);
		if (fc_current->offnum != FirstOffsetNumber)
			elog(ERROR, "failed to add item of size %u to SPGiST index page",
				 fc_innerTuple->size);

		/* 没有父链接需要更新，也没有重定向需要执行 */
		fc_xlrec.offnumParent = InvalidOffsetNumber;
		fc_xlrec.nodeI = 0;

		/* 完成修改新当前缓冲区，标记为脏 */
		MarkBufferDirty(fc_current->buffer);

		/* saveCurrent 不表示不同的缓冲区 */
		fc_saveCurrent.buffer = InvalidBuffer;
	}

	if (RelationNeedsWAL(fc_index) && !fc_state->isBuild)
	{
		XLogRecPtr	fc_recptr;
		int			fc_flags;

		XLogBeginInsert();

		fc_xlrec.nInsert = fc_nToInsert;
		XLogRegisterData((char *) &fc_xlrec, SizeOfSpgxlogPickSplit);

		XLogRegisterData((char *) fc_toDelete,
						 sizeof(OffsetNumber) * fc_xlrec.nDelete);
		XLogRegisterData((char *) fc_toInsert,
						 sizeof(OffsetNumber) * fc_xlrec.nInsert);
		XLogRegisterData((char *) fc_leafPageSelect,
						 sizeof(uint8) * fc_xlrec.nInsert);
		XLogRegisterData((char *) fc_innerTuple, fc_innerTuple->size);
		XLogRegisterData(fc_leafdata, fc_leafptr - fc_leafdata);

		/* 旧叶子页面 */
		if (BufferIsValid(fc_saveCurrent.buffer))
		{
			fc_flags = REGBUF_STANDARD;
			if (fc_xlrec.initSrc)
				fc_flags |= REGBUF_WILL_INIT;
			XLogRegisterBuffer(0, fc_saveCurrent.buffer, fc_flags);
		}

		/* 新叶子页面 */
		if (BufferIsValid(fc_newLeafBuffer))
		{
			fc_flags = REGBUF_STANDARD;
			if (fc_xlrec.initDest)
				fc_flags |= REGBUF_WILL_INIT;
			XLogRegisterBuffer(1, fc_newLeafBuffer, fc_flags);
		}

		/* 内部页面 */
		fc_flags = REGBUF_STANDARD;
		if (fc_xlrec.initInner)
			fc_flags |= REGBUF_WILL_INIT;
		XLogRegisterBuffer(2, fc_current->buffer, fc_flags);

		/* 父页面，如果与内部页面不同 */
		if (fc_parent->buffer != InvalidBuffer)
		{
			if (fc_parent->buffer != fc_current->buffer)
				XLogRegisterBuffer(3, fc_parent->buffer, REGBUF_STANDARD);
			else
				Assert(fc_xlrec.innerIsParent);
		}

		/* 发出 WAL 记录 */
		fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_PICKSPLIT);

		/* 更新所有受影响页面的 LSN */
		if (fc_newLeafBuffer != InvalidBuffer)
		{
			Page		fc_page = BufferGetPage(fc_newLeafBuffer);

			PageSetLSN(fc_page, fc_recptr);
		}

		if (fc_saveCurrent.buffer != InvalidBuffer)
		{
			Page		fc_page = BufferGetPage(fc_saveCurrent.buffer);

			PageSetLSN(fc_page, fc_recptr);
		}

		PageSetLSN(fc_current->page, fc_recptr);

		if (fc_parent->buffer != InvalidBuffer)
		{
			PageSetLSN(fc_parent->page, fc_recptr);
		}
	}

	END_CRIT_SECTION();

	/* 更新本地空闲空间缓存并解锁缓冲区 */
	if (fc_newLeafBuffer != InvalidBuffer)
	{
		SpGistSetLastUsedPage(fc_index, fc_newLeafBuffer);
		UnlockReleaseBuffer(fc_newLeafBuffer);
	}
	if (fc_saveCurrent.buffer != InvalidBuffer)
	{
		SpGistSetLastUsedPage(fc_index, fc_saveCurrent.buffer);
		UnlockReleaseBuffer(fc_saveCurrent.buffer);
	}

	return fc_insertedNew;
}

/*
 * spgMatchNode 操作：下降到当前内部元组的 N'th 子节点
 */
static void fc_spgMatchNodeAction(Relation fc_index, SpGistState *fc_state,
				   SpGistInnerTuple fc_innerTuple,
				   SPPageDesc *fc_current, SPPageDesc *fc_parent, int fc_nodeN)
{
	int			fc_i;
	SpGistNodeTuple fc_node;

	/* 释放先前的父缓冲区（如果有） */
	if (fc_parent->buffer != InvalidBuffer &&
		fc_parent->buffer != fc_current->buffer)
	{
		SpGistSetLastUsedPage(fc_index, fc_parent->buffer);
		UnlockReleaseBuffer(fc_parent->buffer);
	}

	/* 将父节点重新指向当前内部元组的指定节点 */
	fc_parent->blkno = fc_current->blkno;
	fc_parent->buffer = fc_current->buffer;
	fc_parent->page = fc_current->page;
	fc_parent->offnum = fc_current->offnum;
	fc_parent->node = fc_nodeN;

	/* 定位该节点 */
	SGITITERATE(fc_innerTuple, fc_i, fc_node)
	{
		if (fc_i == fc_nodeN)
			break;
	}

	if (fc_i != fc_nodeN)
		elog(ERROR, "failed to find requested node %d in SPGiST inner tuple",
			 fc_nodeN);

	/* 如果有，将当前指向下链接位置 */
	if (ItemPointerIsValid(&fc_node->t_tid))
	{
		fc_current->blkno = ItemPointerGetBlockNumber(&fc_node->t_tid);
		fc_current->offnum = ItemPointerGetOffsetNumber(&fc_node->t_tid);
	}
	else
	{
		/* 下链接为空，因此我们需要寻找新页面 */
		fc_current->blkno = InvalidBlockNumber;
		fc_current->offnum = InvalidOffsetNumber;
	}

	fc_current->buffer = InvalidBuffer;
	fc_current->page = NULL;
}

/*
 * spgAddNode 操作：在当前的内部元组中添加节点
 */
static void fc_spgAddNodeAction(Relation fc_index, SpGistState *fc_state,
				 SpGistInnerTuple fc_innerTuple,
				 SPPageDesc *fc_current, SPPageDesc *fc_parent,
				 int fc_nodeN, Datum fc_nodeLabel)
{
	SpGistInnerTuple fc_newInnerTuple;
	spgxlogAddNode fc_xlrec;

	/* 不应应用于空值 */
	Assert(!SpGistPageStoresNulls(fc_current->page));

	/* 用额外节点构建新内部元组 */
	fc_newInnerTuple = fc_addNode(fc_state, fc_innerTuple, fc_nodeLabel, fc_nodeN);

	/* 准备 WAL 记录 */
	STORE_STATE(fc_state, fc_xlrec.stateSrc);
	fc_xlrec.offnum = fc_current->offnum;

	/* 除非我们需要更改父下链接，否则我们不填写这些 */
	fc_xlrec.parentBlk = -1;
	fc_xlrec.offnumParent = InvalidOffsetNumber;
	fc_xlrec.nodeI = 0;

	/* 除非元组必须移动，否则我们不填写这些 */
	fc_xlrec.offnumNew = InvalidOffsetNumber;
	fc_xlrec.newPage = false;

	if (PageGetExactFreeSpace(fc_current->page) >=
		fc_newInnerTuple->size - fc_innerTuple->size)
	{
		/*
		 * 我们可以就地用新版本替换内部元组
		 */
		START_CRIT_SECTION();

		PageIndexTupleDelete(fc_current->page, fc_current->offnum);
		if (PageAddItem(fc_current->page,
						(Item) fc_newInnerTuple, fc_newInnerTuple->size,
						fc_current->offnum, false, false) != fc_current->offnum)
			elog(ERROR, "failed to add item of size %u to SPGiST index page",
				 fc_newInnerTuple->size);

		MarkBufferDirty(fc_current->buffer);

		if (RelationNeedsWAL(fc_index) && !fc_state->isBuild)
		{
			XLogRecPtr	fc_recptr;

			XLogBeginInsert();
			XLogRegisterData((char *) &fc_xlrec, sizeof(fc_xlrec));
			XLogRegisterData((char *) fc_newInnerTuple, fc_newInnerTuple->size);

			XLogRegisterBuffer(0, fc_current->buffer, REGBUF_STANDARD);

			fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_ADD_NODE);

			PageSetLSN(fc_current->page, fc_recptr);
		}

		END_CRIT_SECTION();
	}
	else
	{
		/*
		 * 将内部元组移动到另一个页面，并更新父节点
		 */
		SpGistDeadTuple fc_dt;
		SPPageDesc	fc_saveCurrent;

		/*
		 * 根页面不应到达这里，因为我们只允许根页面上有一个内部元组，
		 * 且 spgFormInnerTuple 总是检查内部元组不超过页面大小。
		 */
		if (SpGistBlockIsRoot(fc_current->blkno))
			elog(ERROR, "cannot enlarge root tuple any more");
		Assert(fc_parent->buffer != InvalidBuffer);

		fc_saveCurrent = *fc_current;

		fc_xlrec.offnumParent = fc_parent->offnum;
		fc_xlrec.nodeI = fc_parent->node;

		/*
		 * 获取与当前具有相同奇偶性的新的缓冲区，因为它将是
		 * 相同父元组的子节点
		 */
		fc_current->buffer = SpGistGetBuffer(fc_index,
										  GBUF_INNER_PARITY(fc_current->blkno),
										  fc_newInnerTuple->size + sizeof(ItemIdData),
										  &fc_xlrec.newPage);
		fc_current->blkno = BufferGetBlockNumber(fc_current->buffer);
		fc_current->page = BufferGetPage(fc_current->buffer);

		/*
		 * 我们必须确保新的当前缓冲区与旧的不同。 现在
		 * 这是不可能的，但如果 SpGistGetBuffer 变得足够智能 to
		 * 在检查空间之前删除占位元组，也许就不是不可能了。 该情况似乎
		 * 可以工作，除了 WAL 重放可能细微错误，因此我认为仅仅使用 assert 不够
		 * 这里。
		 */
		if (fc_current->blkno == fc_saveCurrent.blkno)
			elog(ERROR, "SPGiST new buffer shouldn't be same as old buffer");

		/*
		 * 新的当前和父缓冲区都将被修改；但请注意，
		 * 父缓冲区可能与新的或旧的当前相同。
		 */
		if (fc_parent->buffer == fc_saveCurrent.buffer)
			fc_xlrec.parentBlk = 0;
		else if (fc_parent->buffer == fc_current->buffer)
			fc_xlrec.parentBlk = 1;
		else
			fc_xlrec.parentBlk = 2;

		START_CRIT_SECTION();

		/* 插入新 ... */
		fc_xlrec.offnumNew = fc_current->offnum =
			SpGistPageAddNewItem(fc_state, fc_current->page,
								 (Item) fc_newInnerTuple, fc_newInnerTuple->size,
								 NULL, false);

		MarkBufferDirty(fc_current->buffer);

		/* 更新父下链接并标记父页面为脏 */
		fc_saveNodeLink(fc_index, fc_parent, fc_current->blkno, fc_current->offnum);

		/*
		 * 用占位符或重定向元组替换旧元组。 除非
		 * 在进行索引构建，否则我们必须插入一个重定向元组以
		 * 处理可能的并发扫描。 反正我们不能仅仅删除它，
		 * 因为那样可能会改变页面上其他元组的偏移量，
		 * 中断其父节点的下链接。
		 */
		if (fc_state->isBuild)
			fc_dt = spgFormDeadTuple(fc_state, SPGIST_PLACEHOLDER,
								  InvalidBlockNumber, InvalidOffsetNumber);
		else
			fc_dt = spgFormDeadTuple(fc_state, SPGIST_REDIRECT,
								  fc_current->blkno, fc_current->offnum);

		PageIndexTupleDelete(fc_saveCurrent.page, fc_saveCurrent.offnum);
		if (PageAddItem(fc_saveCurrent.page, (Item) fc_dt, fc_dt->size,
						fc_saveCurrent.offnum,
						false, false) != fc_saveCurrent.offnum)
			elog(ERROR, "failed to add item of size %u to SPGiST index page",
				 fc_dt->size);

		if (fc_state->isBuild)
			SpGistPageGetOpaque(fc_saveCurrent.page)->nPlaceholder++;
		else
			SpGistPageGetOpaque(fc_saveCurrent.page)->nRedirection++;

		MarkBufferDirty(fc_saveCurrent.buffer);

		if (RelationNeedsWAL(fc_index) && !fc_state->isBuild)
		{
			XLogRecPtr	fc_recptr;
			int			fc_flags;

			XLogBeginInsert();

			/* 原始页面 */
			XLogRegisterBuffer(0, fc_saveCurrent.buffer, REGBUF_STANDARD);
			/* 新页面 */
			fc_flags = REGBUF_STANDARD;
			if (fc_xlrec.newPage)
				fc_flags |= REGBUF_WILL_INIT;
			XLogRegisterBuffer(1, fc_current->buffer, fc_flags);
			/* 父页面（如果与原始和新页面不同） */
			if (fc_xlrec.parentBlk == 2)
				XLogRegisterBuffer(2, fc_parent->buffer, REGBUF_STANDARD);

			XLogRegisterData((char *) &fc_xlrec, sizeof(fc_xlrec));
			XLogRegisterData((char *) fc_newInnerTuple, fc_newInnerTuple->size);

			fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_ADD_NODE);

			/* 我们不担心检查任何这些是否冗余 */
			PageSetLSN(fc_current->page, fc_recptr);
			PageSetLSN(fc_parent->page, fc_recptr);
			PageSetLSN(fc_saveCurrent.page, fc_recptr);
		}

		END_CRIT_SECTION();

		/* 如果它与当前或父页面不同，释放 saveCurrent */
		if (fc_saveCurrent.buffer != fc_current->buffer &&
			fc_saveCurrent.buffer != fc_parent->buffer)
		{
			SpGistSetLastUsedPage(fc_index, fc_saveCurrent.buffer);
			UnlockReleaseBuffer(fc_saveCurrent.buffer);
		}
	}
}

/*
 * spgSplitNode 操作：在当前将内部元组拆分为前缀和后缀
 */
static void fc_spgSplitNodeAction(Relation fc_index, SpGistState *fc_state,
				   SpGistInnerTuple fc_innerTuple,
				   SPPageDesc *fc_current, spgChooseOut *fc_out)
{
	SpGistInnerTuple fc_prefixTuple,
				fc_postfixTuple;
	SpGistNodeTuple fc_node,
			   *fc_nodes;
	BlockNumber fc_postfixBlkno;
	OffsetNumber fc_postfixOffset;
	int			fc_i;
	spgxlogSplitTuple fc_xlrec;
	Buffer		fc_newBuffer = InvalidBuffer;

	/* 不应应用于空值 */
	Assert(!SpGistPageStoresNulls(fc_current->page));

	/* 检查 opclass 是否给出了合理的值 */
	if (fc_out->result.splitTuple.prefixNNodes <= 0 ||
		fc_out->result.splitTuple.prefixNNodes > SGITMAXNNODES)
		elog(ERROR, "invalid number of prefix nodes: %d",
			 fc_out->result.splitTuple.prefixNNodes);
	if (fc_out->result.splitTuple.childNodeN < 0 ||
		fc_out->result.splitTuple.childNodeN >=
		fc_out->result.splitTuple.prefixNNodes)
		elog(ERROR, "invalid child node number: %d",
			 fc_out->result.splitTuple.childNodeN);

	/*
	 * 使用请求的节点数构造新的前缀元组。我们将在下面填充
	 * childNodeN 的下行链接。
	 */
	fc_nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) *
									   fc_out->result.splitTuple.prefixNNodes);

	for (fc_i = 0; fc_i < fc_out->result.splitTuple.prefixNNodes; fc_i++)
	{
		Datum		fc_label = (Datum) 0;
		bool		fc_labelisnull;

		fc_labelisnull = (fc_out->result.splitTuple.prefixNodeLabels == NULL);
		if (!fc_labelisnull)
			fc_label = fc_out->result.splitTuple.prefixNodeLabels[fc_i];
		fc_nodes[fc_i] = spgFormNodeTuple(fc_state, fc_label, fc_labelisnull);
	}

	fc_prefixTuple = spgFormInnerTuple(fc_state,
									fc_out->result.splitTuple.prefixHasPrefix,
									fc_out->result.splitTuple.prefixPrefixDatum,
									fc_out->result.splitTuple.prefixNNodes,
									fc_nodes);

	/* 它必须适合内部元组当前占用的空间 */
	if (fc_prefixTuple->size > fc_innerTuple->size)
		elog(ERROR, "SPGiST inner-tuple split must not produce longer prefix");

	/*
	 * 构造新的后缀元组，包含内部元组的所有节点，具有
	 * 相同的节点数据，但使用 picksplit 函数指定的前缀。
	 */
	fc_nodes = palloc(sizeof(SpGistNodeTuple) * fc_innerTuple->nNodes);
	SGITITERATE(fc_innerTuple, fc_i, fc_node)
	{
		fc_nodes[fc_i] = fc_node;
	}

	fc_postfixTuple = spgFormInnerTuple(fc_state,
									 fc_out->result.splitTuple.postfixHasPrefix,
									 fc_out->result.splitTuple.postfixPrefixDatum,
									 fc_innerTuple->nNodes, fc_nodes);

	/* 如果原始元组是，则后缀元组都是相同的 */
	fc_postfixTuple->allTheSame = fc_innerTuple->allTheSame;

	/* 为 WAL 记录准备数据 */
	fc_xlrec.newPage = false;

	/*
	 * 如果我们不能在当前页面上放下两个元组，则为
	 * 后缀元组获取一个新页面。尤其是，不能拆分到根页面。
	 *
	 * 对于空间计算，注意 prefixTuple 替换内部元组
	 * 但 postfixTuple 将是一个新条目。
	 */
	if (SpGistBlockIsRoot(fc_current->blkno) ||
		SpGistPageGetFreeSpace(fc_current->page, 1) + fc_innerTuple->size <
		fc_prefixTuple->size + fc_postfixTuple->size + sizeof(ItemIdData))
	{
		/*
		 * 选择下一个三重奇偶的页面，因为后缀元组是
		 * 前缀元组的子级
		 */
		fc_newBuffer = SpGistGetBuffer(fc_index,
									GBUF_INNER_PARITY(fc_current->blkno + 1),
									fc_postfixTuple->size + sizeof(ItemIdData),
									&fc_xlrec.newPage);
	}

	START_CRIT_SECTION();

	/*
	 * 用前缀元组替换旧元组
	 */
	PageIndexTupleDelete(fc_current->page, fc_current->offnum);
	fc_xlrec.offnumPrefix = PageAddItem(fc_current->page,
									 (Item) fc_prefixTuple, fc_prefixTuple->size,
									 fc_current->offnum, false, false);
	if (fc_xlrec.offnumPrefix != fc_current->offnum)
		elog(ERROR, "failed to add item of size %u to SPGiST index page",
			 fc_prefixTuple->size);

	/*
	 * 将后缀元组放入适当的页面
	 */
	if (fc_newBuffer == InvalidBuffer)
	{
		fc_postfixBlkno = fc_current->blkno;
		fc_xlrec.offnumPostfix = fc_postfixOffset =
			SpGistPageAddNewItem(fc_state, fc_current->page,
								 (Item) fc_postfixTuple, fc_postfixTuple->size,
								 NULL, false);
		fc_xlrec.postfixBlkSame = true;
	}
	else
	{
		fc_postfixBlkno = BufferGetBlockNumber(fc_newBuffer);
		fc_xlrec.offnumPostfix = fc_postfixOffset =
			SpGistPageAddNewItem(fc_state, BufferGetPage(fc_newBuffer),
								 (Item) fc_postfixTuple, fc_postfixTuple->size,
								 NULL, false);
		MarkBufferDirty(fc_newBuffer);
		fc_xlrec.postfixBlkSame = false;
	}

	/*
	 * 并将前缀元组中的下行指针指向后缀元组。
	 * （我们不能通过反向执行上述两个步骤来避免这一步，
	 * 因为页面上可能没有足够的空间首先插入后缀元组。）
	 * 我们还必须更新前缀元组的本地副本，因为这将写入 WAL。
	 */
	spgUpdateNodeLink(fc_prefixTuple, fc_out->result.splitTuple.childNodeN,
					  fc_postfixBlkno, fc_postfixOffset);
	fc_prefixTuple = (SpGistInnerTuple) PageGetItem(fc_current->page,
												 PageGetItemId(fc_current->page, fc_current->offnum));
	spgUpdateNodeLink(fc_prefixTuple, fc_out->result.splitTuple.childNodeN,
					  fc_postfixBlkno, fc_postfixOffset);

	MarkBufferDirty(fc_current->buffer);

	if (RelationNeedsWAL(fc_index) && !fc_state->isBuild)
	{
		XLogRecPtr	fc_recptr;

		XLogBeginInsert();
		XLogRegisterData((char *) &fc_xlrec, sizeof(fc_xlrec));
		XLogRegisterData((char *) fc_prefixTuple, fc_prefixTuple->size);
		XLogRegisterData((char *) fc_postfixTuple, fc_postfixTuple->size);

		XLogRegisterBuffer(0, fc_current->buffer, REGBUF_STANDARD);
		if (fc_newBuffer != InvalidBuffer)
		{
			int			fc_flags;

			fc_flags = REGBUF_STANDARD;
			if (fc_xlrec.newPage)
				fc_flags |= REGBUF_WILL_INIT;
			XLogRegisterBuffer(1, fc_newBuffer, fc_flags);
		}

		fc_recptr = XLogInsert(RM_SPGIST_ID, XLOG_SPGIST_SPLIT_TUPLE);

		PageSetLSN(fc_current->page, fc_recptr);

		if (fc_newBuffer != InvalidBuffer)
		{
			PageSetLSN(BufferGetPage(fc_newBuffer), fc_recptr);
		}
	}

	END_CRIT_SECTION();

	/* 更新本地空闲空间缓存并释放缓冲区 */
	if (fc_newBuffer != InvalidBuffer)
	{
		SpGistSetLastUsedPage(fc_index, fc_newBuffer);
		UnlockReleaseBuffer(fc_newBuffer);
	}
}

/*
 * 向索引插入一个项目。
 *
 * 成功时返回 true，失败时返回 false（通常由于与
 * 并发插入的冲突）。在后者的情况下，调用者应该使用同样的参数
 * 重新调用 spgdoinsert()。
 */
bool spgdoinsert(Relation fc_index, SpGistState *fc_state,
			ItemPointer fc_heapPtr, Datum *fc_datums, bool *fc_isnulls)
{
	bool		fc_result = true;
	TupleDesc	fc_leafDescriptor = fc_state->leafTupDesc;
	bool		fc_isnull = fc_isnulls[spgKeyColumn];
	int			fc_level = 0;
	Datum		fc_leafDatums[INDEX_MAX_KEYS];
	int			fc_leafSize;
	int			fc_bestLeafSize;
	int			fc_numNoProgressCycles = 0;
	SPPageDesc	fc_current,
				fc_parent;
	FmgrInfo   *fc_procinfo = NULL;

	/*
	 * 查找用户定义的选择函数的 FmgrInfo 一次，以节省
	 * 循环中的周期。
	 */
	if (!fc_isnull)
		fc_procinfo = index_getprocinfo(fc_index, 1, SPGIST_CHOOSE_PROC);

	/*
	 * 准备要插入的叶子数据。
	 *
	 * 如果提供了可选的“压缩”方法，则调用它从输入数据中形成
	 * 叶子关键数据。否则，按原样存储输入数据。由于我们在此 AM 中
	 * 不使用 index_form_tuple，因此我们必须确保要插入的值
	 * 没有被压缩；FormIndexDatum 不保证这一点。但我们假设“压缩”
	 * 方法返回未压缩的值。
	 */
	if (!fc_isnull)
	{
		if (OidIsValid(index_getprocid(fc_index, 1, SPGIST_COMPRESS_PROC)))
		{
			FmgrInfo   *fc_compressProcinfo = NULL;

			fc_compressProcinfo = index_getprocinfo(fc_index, 1, SPGIST_COMPRESS_PROC);
			fc_leafDatums[spgKeyColumn] =
				FunctionCall1Coll(fc_compressProcinfo,
								  fc_index->rd_indcollation[spgKeyColumn],
								  fc_datums[spgKeyColumn]);
		}
		else
		{
			Assert(fc_state->attLeafType.type == fc_state->attType.type);

			if (fc_state->attType.attlen == -1)
				fc_leafDatums[spgKeyColumn] =
					PointerGetDatum(PG_DETOAST_DATUM(fc_datums[spgKeyColumn]));
			else
				fc_leafDatums[spgKeyColumn] = fc_datums[spgKeyColumn];
		}
	}
	else
		fc_leafDatums[spgKeyColumn] = (Datum) 0;

	/* 同样，确保任何 INCLUDE 值没有被压缩 */
	for (int fc_i = spgFirstIncludeColumn; fc_i < fc_leafDescriptor->natts; fc_i++)
	{
		if (!fc_isnulls[fc_i])
		{
			if (TupleDescAttr(fc_leafDescriptor, fc_i)->attlen == -1)
				fc_leafDatums[fc_i] = PointerGetDatum(PG_DETOAST_DATUM(fc_datums[fc_i]));
			else
				fc_leafDatums[fc_i] = fc_datums[fc_i];
		}
		else
			fc_leafDatums[fc_i] = (Datum) 0;
	}

	/*
	 * 计算包含给定数据的叶子元组所需的空间。
	 */
	fc_leafSize = SpGistGetLeafTupleSize(fc_leafDescriptor, fc_leafDatums, fc_isnulls);
	/* 也要考虑一个项目指针 */
	fc_leafSize += sizeof(ItemIdData);

	/*
	 * 如果它不适合，并且 opclass 不能通过后缀减小数据大小，
	 * 那么现在就退出，而不是做很多无用的工作。
	 */
	if (fc_leafSize > SPGIST_PAGE_CAPACITY &&
		(fc_isnull || !fc_state->config.longValuesOK))
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
						fc_leafSize - sizeof(ItemIdData),
						SPGIST_PAGE_CAPACITY - sizeof(ItemIdData),
						RelationGetRelationName(fc_index)),
				 errhint("Values larger than a buffer page cannot be indexed.")));
	fc_bestLeafSize = fc_leafSize;

	/* 将“当前”初始化为适当的根页面 */
	fc_current.blkno = fc_isnull ? SPGIST_NULL_BLKNO : SPGIST_ROOT_BLKNO;
	fc_current.buffer = InvalidBuffer;
	fc_current.page = NULL;
	fc_current.offnum = FirstOffsetNumber;
	fc_current.node = -1;

	/* "parent" 目前是无效的 */
	fc_parent.blkno = InvalidBlockNumber;
	fc_parent.buffer = InvalidBuffer;
	fc_parent.page = NULL;
	fc_parent.offnum = InvalidOffsetNumber;
	fc_parent.node = -1;

	/*
	 * 在进入循环之前，尝试清除任何待处理的中断条件。
	 * 如果查询取消正在进行中，我们现在接受它比后来更好；
	 * 而如果有非取消的条件待处理，在这里处理它可以避免
	 * 重新开始插入并重做所有已完成的工作。
	 */
	CHECK_FOR_INTERRUPTS();

	for (;;)
	{
		bool		fc_isNew = false;

		/*
		 * 如果查询取消正在进行中，则退出。我们必须在循环中
		 * 有这个，因为一个破损的操作类可能会产生一个无限的
		 * picksplit 循环。然而，由于我们在第一次迭代后将持有缓冲区锁，
		 * ProcessInterrupts() 将无法在这里抛出取消错误。
		 * 因此，如果我们看到有中断正在进行，跳出循环并在下面处理情况。
		 * 设置 result = false，因为如果中断不是查询取消或死亡的情况，
		 * 我们必须重新开始插入。
		 */
		if (INTERRUPTS_PENDING_CONDITION())
		{
			fc_result = false;
			break;
		}

		if (fc_current.blkno == InvalidBlockNumber)
		{
			/*
			 * 创建一个叶子页。如果 leafSize 太大而无法适应页面，
			 * 我们实际上还不会使用该页面，但这简化了 doPickSplit 的 API，
			 * 使其始终有一个叶子页可用；所以我们只需静静地将请求限制为页面大小。
			 */
			fc_current.buffer =
				SpGistGetBuffer(fc_index,
								GBUF_LEAF | (fc_isnull ? GBUF_NULLS : 0),
								Min(fc_leafSize, SPGIST_PAGE_CAPACITY),
								&fc_isNew);
			fc_current.blkno = BufferGetBlockNumber(fc_current.buffer);
		}
		else if (fc_parent.buffer == InvalidBuffer)
		{
			/* 我们不持有父页面锁，所以不可能发生死锁 */
			fc_current.buffer = ReadBuffer(fc_index, fc_current.blkno);
			LockBuffer(fc_current.buffer, BUFFER_LOCK_EXCLUSIVE);
		}
		else if (fc_current.blkno != fc_parent.blkno)
		{
			/* 向下到一个新的子页面 */
			fc_current.buffer = ReadBuffer(fc_index, fc_current.blkno);

			/*
			 * 尝试在子页面上获取锁。我们必须小心防止
			 * 与另一个从该页面向下到我们的父页面的插入过程发生死锁
			 * （参见 README）。如果我们无法获得锁，
			 * 放弃插入并告诉调用者重新开始。
			 *
			 * XXX 这可以改进，因为未能在缓冲区上获取锁并不能证明
			 * 发生了死锁情况；锁可能被读者持有，甚至只是后台写入器/检查点
			 * 进程。或许在稍微等待后重试是值得的？
			 */
			if (!ConditionalLockBuffer(fc_current.buffer))
			{
				ReleaseBuffer(fc_current.buffer);
				UnlockReleaseBuffer(fc_parent.buffer);
				return false;
			}
		}
		else
		{
			/* 内部元组可以存储在与父元组相同的页面上 */
			fc_current.buffer = fc_parent.buffer;
		}
		fc_current.page = BufferGetPage(fc_current.buffer);

		/* 不应到达错误类型的页面 */
		if (fc_isnull ? !SpGistPageStoresNulls(fc_current.page) :
			SpGistPageStoresNulls(fc_current.page))
			elog(ERROR, "SPGiST index page %u has wrong nulls flag",
				 fc_current.blkno);

		if (SpGistPageIsLeaf(fc_current.page))
		{
			SpGistLeafTuple fc_leafTuple;
			int			fc_nToSplit,
						fc_sizeToSplit;

			fc_leafTuple = spgFormLeafTuple(fc_state, fc_heapPtr, fc_leafDatums, fc_isnulls);
			if (fc_leafTuple->size + sizeof(ItemIdData) <=
				SpGistPageGetFreeSpace(fc_current.page, 1))
			{
				/* 它适合页面，因此插入它，我们就完成了 */
				fc_addLeafTuple(fc_index, fc_state, fc_leafTuple,
							 &fc_current, &fc_parent, fc_isnull, fc_isNew);
				break;
			}
			else if ((fc_sizeToSplit =
					  fc_checkSplitConditions(fc_index, fc_state, &fc_current,
										   &fc_nToSplit)) < SPGIST_PAGE_CAPACITY / 2 &&
					 fc_nToSplit < 64 &&
					 fc_leafTuple->size + sizeof(ItemIdData) + fc_sizeToSplit <= SPGIST_PAGE_CAPACITY)
			{
				/*
				 * 数据量相当小，因此只需将整个链移动到另一个叶子页 
				 * 而不是将其拆分。
				 */
				Assert(!fc_isNew);
				fc_moveLeafs(fc_index, fc_state, &fc_current, &fc_parent, fc_leafTuple, fc_isnull);
				break;			/* 我们完成了 */
			}
			else
			{
				/* picksplit */
				if (fc_doPickSplit(fc_index, fc_state, &fc_current, &fc_parent,
								fc_leafTuple, fc_level, fc_isnull, fc_isNew))
					break;		/* doPickSplit 安装了新的元组 */

				/* 叶子元组尚未插入 */
				pfree(fc_leafTuple);

				/*
				 * 当前现在描述新的内部元组，去插入它
				 */
				Assert(!SpGistPageIsLeaf(fc_current.page));
				goto process_inner_tuple;
			}
		}
		else					/* 非叶子页面 */
		{
			/*
			 * 应用操作类选择函数以确定如何将给定数据项插入到当前内部元组中。
			 */
			SpGistInnerTuple fc_innerTuple;
			spgChooseIn fc_in;
			spgChooseOut fc_out;

			/*
			 * spgAddNode 和 spgSplitTuple 情况将循环回这里以
			 * 完成插入操作。以备不时之需，如果选择
			 * 函数出现故障并反复产生添加或拆分请求，请检查查询取消（参见上述评论）。
			 */
	process_inner_tuple:
			if (INTERRUPTS_PENDING_CONDITION())
			{
				fc_result = false;
				break;
			}

			fc_innerTuple = (SpGistInnerTuple) PageGetItem(fc_current.page,
														PageGetItemId(fc_current.page, fc_current.offnum));

			fc_in.datum = fc_datums[spgKeyColumn];
			fc_in.leafDatum = fc_leafDatums[spgKeyColumn];
			fc_in.level = fc_level;
			fc_in.allTheSame = fc_innerTuple->allTheSame;
			fc_in.hasPrefix = (fc_innerTuple->prefixSize > 0);
			fc_in.prefixDatum = SGITDATUM(fc_innerTuple, fc_state);
			fc_in.nNodes = fc_innerTuple->nNodes;
			fc_in.nodeLabels = spgExtractNodeLabels(fc_state, fc_innerTuple);

			memset(&fc_out, 0, sizeof(fc_out));

			if (!fc_isnull)
			{
				/* 使用用户定义的选择方法 */
				FunctionCall2Coll(fc_procinfo,
								  fc_index->rd_indcollation[0],
								  PointerGetDatum(&fc_in),
								  PointerGetDatum(&fc_out));
			}
			else
			{
				/* 强制“匹配”操作（插入到随机子节点） */
				fc_out.resultType = spgMatchNode;
			}

			if (fc_innerTuple->allTheSame)
			{
				/*
				 * 不允许在所有相同的元组上执行 AddNode。
				 * Opclass 必须说明 “匹配”，在这种情况下我们选择一个随机
				 * 的节点进行深入，或者 “拆分”。
				 */
				if (fc_out.resultType == spgAddNode)
					elog(ERROR, "cannot add a node to an allTheSame inner tuple");
				else if (fc_out.resultType == spgMatchNode)
					fc_out.result.matchNode.nodeN =
						pg_prng_uint64_range(&pg_global_prng_state,
											 0, fc_innerTuple->nNodes - 1);
			}

			switch (fc_out.resultType)
			{
				case spgMatchNode:
					/* 深入到第 N 个子节点 */
					fc_spgMatchNodeAction(fc_index, fc_state, fc_innerTuple,
									   &fc_current, &fc_parent,
									   fc_out.result.matchNode.nodeN);
					/* 根据 opclass 的要求调整级别 */
					fc_level += fc_out.result.matchNode.levelAdd;
					/* 替换 leafDatum 并重新计算 leafSize */
					if (!fc_isnull)
					{
						fc_leafDatums[spgKeyColumn] = fc_out.result.matchNode.restDatum;
						fc_leafSize = SpGistGetLeafTupleSize(fc_leafDescriptor,
														  fc_leafDatums, fc_isnulls);
						fc_leafSize += sizeof(ItemIdData);
					}

					/*
					 * 检查新的元组大小；如果它不能适应则失败，除非
					 * opclass 说它可以通过后缀处理这种情况。
					 *
					 * 然而，opclass 只能缩短叶数据，
					 * 这可能不足以使元组适合，
					 * 因为 INCLUDE 列可能单独使用超过一个页面。
					 * 根据 opclass 的行为，这可能导致
					 * 无限循环——例如，spgtextproc.c 将
					 * 在数据用尽后不断生成空字符串的叶数据。
					 * opclasses 中的实际错误
					 * 也可能导致无限循环。为了检测这样的
					 * 循环，请检查每次是否通过
					 * 减少 leafSize 来取得进展。这有点
					 * 困难。不过，由于对齐考虑，
					 * 总元组大小可能不会在每次迭代中减少。
					 * 此外，有边缘情况，选择方法
					 * 可能似乎在循环一两次中没有取得进展。
					 * 有点随意，我们允许最多 10 次无进展
					 * 迭代后再失败。（这个限制应该超过
					 * MAXALIGN，以适应每次从叶数据中修剪一个
					 * 字节的 opclasses。）
					 */
					if (fc_leafSize > SPGIST_PAGE_CAPACITY)
					{
						bool		fc_ok = false;

						if (fc_state->config.longValuesOK && !fc_isnull)
						{
							if (fc_leafSize < fc_bestLeafSize)
							{
								fc_ok = true;
								fc_bestLeafSize = fc_leafSize;
								fc_numNoProgressCycles = 0;
							}
							else if (++fc_numNoProgressCycles < 10)
								fc_ok = true;
						}
						if (!fc_ok)
							ereport(ERROR,
									(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
									 errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
											fc_leafSize - sizeof(ItemIdData),
											SPGIST_PAGE_CAPACITY - sizeof(ItemIdData),
											RelationGetRelationName(fc_index)),
									 errhint("Values larger than a buffer page cannot be indexed.")));
					}

					/*
					 * 循环并尝试在 “current” 位置插入新的 leafDatum
					 * （这可能引用一个现有的子
					 * 元组，也可能无效，迫使我们为元组找到一个新
					 * 页面）。
					 */
					break;
				case spgAddNode:
					/* 如果节点没有标签，AddNode 是不合理的 */
					if (fc_in.nodeLabels == NULL)
						elog(ERROR, "cannot add a node to an inner tuple without node labels");
					/* 根据请求将节点添加到内元组中 */
					fc_spgAddNodeAction(fc_index, fc_state, fc_innerTuple,
									 &fc_current, &fc_parent,
									 fc_out.result.addNode.nodeN,
									 fc_out.result.addNode.nodeLabel);

					/*
					 * 重试插入到扩大的节点中。我们假设
					 * 这次会得到 MatchNode 的结果。
					 */
					goto process_inner_tuple;
					break;
				case spgSplitTuple:
					/* 根据请求拆分内元组 */
					fc_spgSplitNodeAction(fc_index, fc_state, fc_innerTuple,
									   &fc_current, &fc_out);

					/* 重试插入到拆分的节点中 */
					goto process_inner_tuple;
					break;
				default:
					elog(ERROR, "unrecognized SPGiST choose result: %d",
						 (int) fc_out.resultType);
					break;
			}
		}
	}							/* 结束循环 */

	/*
	 * 释放我们仍在持有的任何缓冲区。注意可能性
	 * 当前和父级引用同一缓冲区。
	 */
	if (fc_current.buffer != InvalidBuffer)
	{
		SpGistSetLastUsedPage(fc_index, fc_current.buffer);
		UnlockReleaseBuffer(fc_current.buffer);
	}
	if (fc_parent.buffer != InvalidBuffer &&
		fc_parent.buffer != fc_current.buffer)
	{
		SpGistSetLastUsedPage(fc_index, fc_parent.buffer);
		UnlockReleaseBuffer(fc_parent.buffer);
	}

	/*
	 * 我们不支持在某些外部函数持有缓冲区锁时被调用
	 * （或任何其他原因推迟查询取消）。如果情况是这样，
	 * 告诉调用者重试将会导致一个无限循环。
	 */
	Assert(INTERRUPTS_CAN_BE_PROCESSED());

	/*
	 * 最后，再次检查中断。如果有查询取消，
	 * ProcessInterrupts() 将能够在这里抛出错误。如果是
	 * 其他类型的中断，只需清除，返回 false 告诉我们的调用者重试。
	 */
	CHECK_FOR_INTERRUPTS();

	return fc_result;
}
